#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<string>
#include<queue>
#include<unordered_set>
#include<unordered_map>
#include<algorithm>

using namespace std;

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;




//int main()
//{
//	int n, k, p;
//	cin >> n >> k >> p;
//	vector<int> t(n), d(n);
//	for (int i = 0; i < n; i++) cin >> t[i];
//	for (int i = 0; i < n; i++) cin >> d[i];
//	vector<int> dp(n), dmax(n);
//	unordered_map<int, int> hash;
//
//	dp[0] = d[0];
//	hash[t[0]] = 0;
//	int ret = 0;
//	for (int i = 1; i < n; i++)
//	{
//		if (!hash.count(t[i])) hash[t[i]] = i;
//		dp[i] = dp[i - 1] + d[i];
//		int a = t[i];
//		if (hash.count(a))
//		{
//			dmax[i] = max(dmax[i], dp[i] - dp[hash[a]] + d[hash[a]]);
//		}
//		ret = max(ret, dmax[i]);
//	}
//	cout << ret << endl;
//	return 0;
//}


//bool judge(const string& s, const string& t)
//{
//	string t1, t2;
//	for (auto& ch : s)
//	{
//		if (ch == 'X') t1 += ch;
//		else t1 += "XX";
//	}
//	for (auto& ch : t)
//	{
//		if (ch == 'X') t2 += ch;
//		else t2 += "XX";
//	}
//	int cur1 = 0, cur2 = 0;
//	while (cur1 < t1.size() && cur2 < t2.size())
//	{
//		if (t1[cur1++] != t2[cur2++]) return false;
//	}
//	if (t1.size() == t2.size()) return true;
//	if (cur1 == t1.size())
//	{
//		return t2.size() - cur2 == 6;
//	}
//	if (cur1 == t2.size())
//	{
//		return t1.size() - cur1 == 6;
//	}
//	return true;
//}
//


//bool judge(const string& s, const string& t)
//{
//	string t1, t2;
//	for (auto& ch : s)
//	{
//		if (ch == 'X') t1 += ch;
//		else t1 += "XX";
//	}
//	for (auto& ch : t)
//	{
//		if (ch == 'X') t2 += ch;
//		else t2 += "XX";
//	}
//	int cur1 = 0, cur2 = 0;
//	while (cur1 < t1.size() && cur2 < t2.size())
//	{
//		if (t1[cur1++] != t2[cur2++]) return false;
//	}
//	if (t1.size() == t2.size()) return true;
//	if (cur1 == t1.size())
//	{
//		return t2.size() - cur2 == 6;
//	}
//	if (cur1 == t2.size())
//	{
//		return t1.size() - cur1 == 6;
//	}
//	return true;
//}
//
//int main()
//{
//	string s, t;
//	cin >> s >> t;
//	int q, a, b, c, d;
//	cin >> q;
//	for (int i = 0; i < q; i++)
//
//	{
//		cin >> a >> b >> c >> d;
//		string t1 = s.substr(a - 1, b - a + 1);
//		string t2 = t.substr(c - 1, d - c + 1);
//		if (judge(t1, t2)) cout << "YES" << endl;
//		else cout << "NO" << endl;
//	}
//	return 0;
//}
 

// 
//struct cmp
//{
//	bool operator()(string& s1,string& s2) {
//		int num1 = 0, num2 = 0;
//		for (auto& ch : s1) num1 += ch - 'a' + 1;
//		for (auto& ch : s2) num2 += ch - 'a' + 1;
//		if(num1 == num2) return s1 > s2;
//		return num1 > num2;
//	}
//};
//
//int main()
//{
//	string s;
//	int k;
//	cin >> s >> k;
//	priority_queue<string, vector<string>, cmp> pq;
//	for (int i = 0; i < s.size(); i++)
//	{
//		for (int j = s.size() - i; j >= 1; j--)
//		{
//			string t = s.substr(i, j);
//			pq.push(t);
//			if (pq.size() > k) pq.pop();
//		}
//	}
//
//	cout << pq.top() << endl;
//	return 0;
//}

//int main()
//{
//	string s;
//	int k;
//	cin >> s >> k;
//	priority_queue<string, vector<string>, cmp> pq;
//	unordered_set<string> hash;
//	for (int i = 0; i < s.size(); i++)
//	{
//		for (int j = s.size() - i; j >= 1; j--)
//		{
//			string t = s.substr(i, j);
//			hash.insert(t);
//		}
//	}
//	for (auto& v : hash)
//	{
//		pq.push(v);
//		if (pq.size() > k) pq.pop();
//	}
//
//	cout << pq.top() << endl;
//	return 0;
//}


//int main()
//{
//	string s;
//	cin >> s;
//	s += s;
//	string ret = s.substr(3, 7);
//	string ans;
//	for (auto& ch : ret)
//	{
//		int tmp = ch;
//		ans += to_string(tmp);
//	}
//	cout << ans << endl;
//	return 0;
//}